/*
 * QuickSort.h
 *
 *  Created on: 2012-10-26
 *      Author: user
 */

#ifndef QUICKSORT_H_
#define QUICKSORT_H_
#include <iostream>
using namespace std;

//quick sort,
//parameter: start, the first item index of array
//           end, the last item index of array
void quickSort(int *n, int start, int end)
{
	if (start > end)
	{
		return;
	}

	int mid = start;

	int i = start + 1;
	int j = end;
	for (; i < j; )
	{
		if (n[i] > n[mid])
		{
			if (n[j] < n[mid]) //swap the data
			{
				int temp = n[i];
				n[i] = n[j];
				n[j] = temp;
				i++;
				j--;
			}
			else
			{
				j--;
			}
		}
		else
		{
			i++;
		}
	}

	if (i != mid + 1 || j == end)
	{
		int temp = n[mid];
		n[mid] = n[i];
		n[i] = temp;
	}


	quickSort(n, 0, i -1);
	quickSort(n, i + 1, end);
}

void quickSortTest()
{
	int a[5] = {3, 2, 4, 1, 6};

	quickSort(a, 0, 4);

	for (int i = 0; i < 5; i++)
	{
		cout << a[i] << endl;
	}
}

#endif /* QUICKSORT_H_ */
